package com.douma.第16天;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 抖码算法，让算法学习变的简单有趣
 *
 * @作者 : 老汤
 */
public class 找单词 {

    private static char[][] board;
    private static String word;

    private static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static int n;
    private static boolean[][] visited;

    private static List<int[]> res = new ArrayList<>();

    // 这道题目是力扣原题的变形题，对应的力扣 79 号算法题： 单词搜索
    // 视频讲解请见：课程 B：https://appvpmptkl94774.pc.xiaoe-tech.com/p/t_pc/goods_pc_detail/goods_detail/course_2JhpjhhCEEuVZyqeXrr5thZAT2q
    // 【刷题篇第 23 天：回溯算法（二）】 第 5 节
    // 不过你要是想看懂回溯算法的话，请先学习课程 B【刷题篇第 22 天：回溯算法（一）】
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        sc.nextLine();
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            String[] chars = sc.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                board[i][j] = chars[j].toCharArray()[0];
            }
        }
        word = sc.nextLine();

        visited = new boolean[n][n];

        for (int row = 0; row < n; row++) {
            boolean hasFound = false;
            for (int col = 0; col < n; col++) {
                if (board[row][col] == word.charAt(0)) {
                    if (dfs(row, col, 0, new ArrayList<>())) {
                        hasFound = true;
                        break;
                    }
                }
            }
            if (hasFound) break;
        }

        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i)[0] + ",");
            if (i == res.size() - 1) {
                System.out.print(res.get(i)[1]);
            } else {
                System.out.print(res.get(i)[1] + ",");
            }
        }
        System.out.println();

        sc.close();
    }

    // list 记住符合单词顺序的字符对应的下标值
    private static boolean dfs(int row, int col, int index, List<int[]> list) {
        if (board[row][col] != word.charAt(index)) return false;
        else if (index == word.length() - 1) {
            // 找到了符合单词顺序的所有字符
            list.add(new int[]{row, col});
            res = new ArrayList<>(list);
            return true;
        }

        // 将当前字符所在的索引放入结果集
        list.add(new int[]{row, col});

        visited[row][col] = true;
        for (int[] dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if (nextRow >= 0 && nextRow < n && nextCol >= 0 && nextCol < n
                    && !visited[nextRow][nextCol]) {
                if (dfs(nextRow, nextCol, index + 1, list)) return true;
            }
        }

        // 回溯
        list.remove(list.size() - 1);
        visited[row][col] = false;
        return false;
    }

}
